In order for OFDMA systems to work properly on the uplink, the signals transmitted by the multiple mobile subscriber (MS) terminals within the system must arrive at the base station (BS) synchronously. An initial ranging process is performed to achieve an initial synchronization to the system and then a periodic ranging is performed to track and maintain the synchronization.
In the process of initial ranging, the first step once a mobile subscriber terminal joins the system is to first acquire the downlink timing of the system. Generally the mobile subscriber does this by synchronizing to a preamble signal transmitted by the base station on the downlink. The mobile subscriber then transmits a special signal referred to as an initial ranging transmission. It transmits this signal with respect to its acquired downlink timing. The base station will search for the initial ranging transmissions. This is a multiple access situation where multiple mobile subscriber terminals may be trying to access the system and the base station is unaware that any of the terminals are transmitting. The search will not only detect if an MS is present but will also allow the base station to estimate the range, or the distance, of the mobile subscriber with respect to the base station. This information is communicated to the mobile subscriber which will then adjust the timing of its following transmissions such that they are received synchronously with all of the other mobile subscriber terminals in the system. Note that if the detection process fails the mobile subscriber will wait a set period of time and re-transmit with more power.
In OFDMA systems, ranging is used to achieve synchronization of mobile subscriber (MS) terminals on the uplink. Once a mobile subscriber (e.g. a cell phone or other wireless device) has acquired the downlink timing of the system, the mobile subscriber generates an initial ranging transmission. The mobile subscriber transmits with respect to its acquired downlink timing. The delay of the signal received at the base station (BS) with respect to its reference time (which is generally GPS-derived) will correspond to the round-trip-delay (RTD) of a signal traveling between the base station and mobile subscriber.
The initial ranging transmission has a particular structure in both the time and frequency dimensions. The IEEE 802.16 standard, which is hereby incorporated by reference, defines an initial ranging transmission as occurring over 2 or 4 OFDMA symbols. This patent disclosure will adopt the 2 OFDMA symbol option although it is a straightforward generalization to the 4 OFDMA symbol case. The mobile subscriber chooses a code of length 144 bits which it transmits as BPSK symbols over 144 sub-carriers that are distributed across the frequency dimension. The code is randomly chosen from a set of possible codes.
FIG. 1 shows the time-domain structure of the initial ranging transmission in a situation where the cyclic prefix (CP) of the OFDM symbol is chosen to be ⅛th of the useful OFDM symbol. FIG. 1 shows how, in the time domain, the samples 6 of the initial ranging transmission are copied from the first OFDMA symbol 2 to create both the cyclic prefix 8 and the second OFDMA symbol 4 with the 2nd OFDMA symbol structured in such a way that it is phase continuous with respect to the 1st OFDMA symbol. Of particular interest is the fact that there is a periodicity in the signal (due to the phase continuity) with a period of the FFT size.
The base station performs signal processing on its received signal to detect any initial ranging transmissions over the set of possible codes and over a search window of possible delays. The search window size corresponds to the cell size. The goal of the base station is to detect the transmission from any mobile subscriber that is transmitting an initial ranging code and to detect the range of the user. A good detector will be able to detect successfully at a low signal-to-noise ratio (SNR) and under a wide variety of possible channel conditions. The cost of not detecting an initial ranging transmission is that the mobile subscriber will need to re-transmit with a higher power some time later. This re-transmission adds interference to the system as well as increasing the time required for the mobile subscriber to enter the system.
As with any detection problem, false detections are possible and should be minimized. Generally, the cost of a false detection is some downlink control channel bandwidth used to signal to the mobile subscriber its ranging adjustment. Eventually, the base station will recognize that a false detection has occurred when no response is received from a mobile subscriber.
The detection must occur in the presence of several impairments. First there is additive noise. Second, the ranging transmission will be affected by the multi-path environment of the wireless channel. Finally, the ranging transmission will experience interference. Two such sources of interference are the initial ranging transmissions of other mobile subscriber terminals and simultaneous data transmissions from other mobile subscriber terminals. This interference can be significant as the orthogonality of the OFDMA signal structure is lost when the signals are received asynchronously (which they will be for the initial ranging transmission). This interference is referred to as inter-carrier interference (ICI).
As shown in FIG. 2, the prior-art method 10 of performing initial ranging detection involves the following three steps. After samples are received into the buffer 12, the first step is to remove the cyclic prefix (CP) 14 and then perform FFTs 16 aligned with the reference data timing. The output is:
      α    ⁢                  ⁢          (      k      )        =      C    ⁢                  ⁢                  ∑                  n          =          0                                      N            FFT                    -          1                    ⁢                          ⁢              r        ⁢                                  ⁢                              (            n            )                    ·                      ⅇ                                          -                j                            ⁢                                                          ⁢              2              ⁢              π              ⁢                                                          ⁢              kn              ⁢                              /                            ⁢                              N                FFT                                                        
where,                C is a scaling factor,        NFFT is the FFT size,        r(n) is the received sample with index n=0 corresponding to the first sample after the CP,        k is the FFT output bin (i.e. sub-carrier index).        
The second step of this prior-art method is to take the output of the 2nd FFT and select the initial ranging sub-carriers for further processing. As shown in FIG. 3, the initial ranging transmission is offset by a delay equal to the mobile subscriber's round-trip delay (MS RTD 30), so that the portion 32 of the initial ranging transmission processed in the FFT corresponding to the 2nd OFMDA symbol would encompass a portion of the 1st OFDMA symbol and a portion of the 2nd OFDMA symbol.
The sub-carriers are distributed across the frequency dimension with the indices kε(0, . . . , NFFT−1). Due to the time-domain structure of the initial ranging transmission, there will always be a full OFDMA symbol's worth of transmitted samples to process with the samples circularly shifted in time which will correspond to a phase shift between consecutive sub-carriers. Also, since the FFT is done over the same samples as the data, there is no inter-carrier interference from the data sub-carriers. In fact, this point is the rationale for performing the FFT over the set of samples corresponding to the 2nd FFT. This is illustrated in FIG. 3.
The third step of this prior-art method is to use a search window 18 to perform a search across the search window of delays, which in turn is performed in three sub-steps: first, for delay d, multiply the initial ranging sub-carriers by a phase factor (phase shift 20) that depends on the sub-carrier index k and the delay d (this can also be done recursively):φp(k,d)=α(k)·ej2πk(d+1)−(NFFT−Ng)/NFFT 
where,                φ(k,d) is the resulting phase-shifted sub-carrier value for sub-carrier k for delay d,        k is the sub-carrier index of the corresponding initial ranging sub-carrier,        d is the delay (in units of samples) being searched (d=0, 1, . . . , Nsearch−1)        NFFT is the FFT size, and        Ng is the size of the guard duration (CP duration in samples).        
Second, using a correlator 22, the resulting phase-shifted sub-carriers are correlated with the set of ranging codes being searched. This correlation could be done all coherently:
      γ    ⁢                  ⁢          (              m        ,        d            )        =                                    ∑                      n            =            0                    143                ⁢                                  ⁢                  φ          ⁢                                          ⁢                                    (                                                f                  ⁡                                      (                    n                    )                                                  ,                d                            )                        ·                          c              m                                ⁢                                          ⁢                      (            n            )                                      2  
where,                γ(m,d) is the correlation output for code m at delay d,        n is an index through the code (n=0, . . . , 143),        f(n) is the function that describes the mapping of the code to the sub-carrier indices,        cm(n) is the bit of code m at index n.        
Third, the maximum correlation result is found for each code and compared against a predetermined threshold. Detection for a particular code is considered a success if the correlation result exceeds the threshold and the range is then determined to be the argument (i.e. the delay) that maximizes the correlation result. Note that the threshold is normally based on a multiple of an estimated noise level with the optimum value of the threshold determined through empirical testing or simulation. As shown in FIG. 2, a noise estimator 24 can be used with comparator logic 26 to determine if the maximum correlation result exceeds the threshold in order to declare a successful detection.
One of the shortcomings of this prior-art method is that initial ranging detection at low SNR and/or in poor channel conditions has a low probability of successful detection. As a consequence, the mobile subscriber retransmits its initial ranging transmission at a higher power, both draining the mobile's battery power and creating inter-carrier interference because the initial ranging transmission is not synchronized (i.e. not orthogonal). A technology that addresses this problem remains highly desirable.